#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool IsSubStr(char newS[], int len, int n, char *p, int* removable)
{
    int i = 0;
    int newSLen = strlen(newS);
    int j = 0;
    char newScpy[len + 1];
    strcpy(newScpy, newS);
    for (i = 0; i <= n; i++) {
        newScpy[removable[i]] = ' ';
    }
    i = 0;
    while (i != newSLen) {
        if (newScpy[i] == p[j]) {
            i++;
            j++;
        } else {
            i++;
        }
        if (p[j] == '\0') {
            return true;
        }
    }
    return false;
}
int maximumRemovals(char * s, char * p, int* removable, int removableSize){
    if (s == NULL) {
        return removableSize;
    }
    int i;
    int len = strlen(s);
    int end = removableSize;
    i = 0;
    // 时间复杂度需要优化，使用二分法
    while (i < end) {
        if (!IsSubStr(s, len, (i + end) / 2, p, removable)) {
            if (IsSubStr(s, len, (i + end) / 2 - 1, p, removable)) {
                return (i + end) / 2;;
            }
            end = (i + end) / 2;
        } else {
            i = (i + end) / 2 + 1;
        }
    }
    return removableSize;
}

int main()
{
    char *s = "abcacb", *p = "ab";
    int removable[3] = {3,1,0};
    int ret  = maximumRemovals(s, p, removable, 3);
    printf("%d", ret);
}
